/**
 * @author: li_jian
 * @version: 1.0
 * @date: 2020/7/7 01:36
 * @description： @link{https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking}
 */
public class JZ10_矩形覆盖 {

    public int RectCover(int target) {
        return rectCoverWithFor(target);
    }

    /**
     * 使用for循环实现
     * @param target
     * @return
     */
    private int rectCoverWithFor(int target) {
        if (target <= 2)
            return target;

        int pre2 = 1, pre1 = 2;
        int ret = 0;
        for (int i = 3; i <= target; i++) {
            ret = pre2 + pre1;
            pre2 = pre1;
            pre1 = ret;
        }

        return ret;
    }


    /**
     * 递归实现
     *
     * @param target
     * @return
     */
    private int rectCoverWithRecursion(int target) {
        if (target <= 2)
            return target;

        return rectCoverWithRecursion(target - 1) + rectCoverWithRecursion(target - 2);
    }
}
